package com.togo.algorithm.medium.array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @Author taiyn
 * @Description TODO
 * @Date 下午11:13 2022/4/6
 **/
public class No128 {

    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return 1;
        Arrays.sort(nums);
        int max = 1;
        int count = 1;
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i + 1] == nums[i]) continue;

            if(nums[i + 1] - nums[i] == 1) count++;
            else{
                max = Math.max(max, count);
                count = 1;
            }
        }

        max = Math.max(max, count);
        return max;
    }

    /**
     * 不排序, 暴力解法是两层循环一个一个比较, 但是这样其实有冗余情况.
     * 我们只需要从一个序列中最小的开始找就可以, 碰到中间的数可以直接跳过.
     * 即i-1不存在则表示i就是某个序列最小的数, 反之则表示i是某个序列中间的数, 可以跳过
     * @param nums
     * @return
     */
    public int longestConsecutive_2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i : nums) {
            set.add(i);
        }

        int result = 0;
        for(int i : set) {

            // 不包含说明i是某序列的最小值
            if(!set.contains(i - 1)) {
                int size = 1;
                int n = i + 1;
                while(set.contains(n)) {
                    size++;
                    n++;
                }
                result = Math.max(size, result);
            }
        }

        return result;
    }

    public static void main(String[] args) {

        char c = '0';
        int a = c;
        System.out.println(a);
        System.out.println((int) '1');
//        int[] nums = new int[]{100,4,200,1,3,2};
//        No128 no128 = new No128();
//        no128.longestConsecutive(nums);
    }
}
